package DataStructureAndAlgorithm.AcWing_每日一题.BFS;


//链接：https://www.acwing.com/problem/content/description/3799/
//对删除每个数字出现的各种情况进行广搜即可
import java.util.*;

class AcWing_3796{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int k = 0; k < t; k++){
            int n = in.nextInt();
            if (isSqrt(n))System.out.println(0);
            else {
                Queue<Integer> queue = new LinkedList<>();
                int cnt = 0;
                queue.offer(n);
                boolean isOk = false;
                while (!queue.isEmpty()){
                    int size = queue.size();
                    cnt++;
                    for (int i = 0; i < size; i++){
                        int temp = queue.poll();
                        int len = getLen(temp);
                        String str = String.valueOf(temp);
                        for (int j = 0; j < str.length(); j++){
                            String s = str.substring(0,j) + str.substring(j + 1,str.length());
                            if (s.length() == 0)break;
                            int num = Integer.parseInt(s);
                            if (getLen(num) == len - 1 && num != 0){
                                if (isSqrt(num)){
                                    isOk = true;
                                    System.out.println(cnt);
                                    break;
                                }else {
                                    queue.offer(num);
                                }
                            }
                        }
                        if (isOk)break;
                    }
                    if (isOk)break;
                }
                if (!isOk)System.out.println(-1);

            }
        }


        in.close();
    }

    static int getLen(int n){
        if (n % 10 == 0)n++;
        int cnt = 0;
        while (n != 0){
            cnt ++;
            n /= 10;
        }
        return cnt;
    }

    static boolean isSqrt(int n){
        int pow = (int)Math.sqrt(n);
        return pow * pow == n;
    }
}